package algorithm;

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;

public class UnionFindService {
    private Integer count;//当前连接集合数量
    private Integer[] id;//节点父连接数组
    private Integer[] childNum;//节点的子节点
    private Integer[][] connectPairs;//待处理的连接数组




    //原数据 存储list (去重）
    public List<String> originList=new ArrayList<>();

    public UnionFindService() {

    }

    public UnionFindService(Integer nodeNum, String strPairs) {
        this.count = nodeNum;
        this.id = new Integer[this.count];
        this.childNum = new Integer[this.count];
        createArray();
        dealConnectPairs(strPairs);
        getUnion();
    }

    /**
     * 获取
     * @param inputFile 输入数据文件地址
     */
    public void createArray(String inputFile) {
        List<Integer> idList=new ArrayList<>();
        List<Integer> childNumList= new ArrayList<>();
        //创建初始化节点和子节点数目
        try {
            List<String> arrys =  Files.readAllLines(Paths.get(inputFile));
            Integer pairsNum = arrys.size();
            this.count=pairsNum;
            this.connectPairs = new Integer[pairsNum][2];
            int pairIdex = 0;
            for(String varr:arrys){
                String[] strs = varr.split(",");
                //组计数
                int groupNum = 0;
                // -----part1----- 配对数组计数
                int groupNumPair=0;
                if(!originList.contains(strs[0])){
                    originList.add(strs[0]);
                    int idex= originList.indexOf(strs[0]);
                    idList.add(idex);
                    childNumList.add(1);
                }
                groupNum=originList.indexOf(strs[0]);


                // -----part2----- 配对数组计数
                if(!originList.contains(strs[1])){
                    originList.add(strs[1]);
                    int idex= originList.indexOf(strs[1]);
                    idList.add(idex);
                    childNumList.add(1);
                }
                groupNumPair=originList.indexOf(strs[1]);

                //-------设置关联组数据------
                this.connectPairs[pairIdex][0] = groupNum;
                this.connectPairs[pairIdex][1] = groupNumPair;

                pairIdex++;
            }
            id=idList.toArray(new Integer[idList.size()]);
            childNum=childNumList.toArray(new Integer[childNumList.size()]);
            arrys=null;
        } catch (Exception e) {
            e.printStackTrace();
        }

    }


    private void createArray() {
        //创建初始化节点和子节点数目
        for (int i = 0; i < this.count; i++) {
            this.id[i] = i;
            this.childNum[i] = 1;
        }
    }



    private void dealConnectPairs(String connectPairs) {
        //创建待连接的数字
        //如果以竖线为分隔符，则split的时候需要加上两个斜杠【\\】进行转义
        String[] pairs = connectPairs.split("\\|");
        Integer pairsNum = pairs.length / 2;
        this.connectPairs = new Integer[pairsNum][2];
        for (int i = 0, j = 0; i < pairsNum; i++) {
            this.connectPairs[i][0] = Integer.parseInt(pairs[j++]);
            this.connectPairs[i][1] = Integer.parseInt(pairs[j++]);
        }
    }

    public Integer getCount() {
        return count;
    }

    public Integer[] getId() {
        return id;
    }

    public Integer[] getChildNum() {
        return childNum;
    }

    public Integer find(int currentIndex) {
        //循环查找父节点
        int root = currentIndex;
        while (root != this.id[root]) {
            root = this.id[root];
        }
        //路径压缩，将节点的全部父节点都指向r，把路径压缩成深度是1的树
        int parentIndex = currentIndex, tmp;
        while (parentIndex != root) {
            tmp = this.id[parentIndex];
            this.id[parentIndex] = root;
            parentIndex = tmp;
        }
        return root;
    }

    public Boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public void getUnion() {
        for (Integer[] connectPair : this.connectPairs) {
            this.union(connectPair[0], connectPair[1]);
        }
    }

    private void union(int p, int q) {
        Integer i = this.find(p);
        Integer j = this.find(q);
        if (!i.equals(j)) {
            if (this.childNum[i] > this.childNum[j]) {
                id[j] = i;
                this.childNum[i] += this.childNum[j];
            } else {
                id[i] = j;
                this.childNum[j] += this.childNum[i];
            }
            this.count--;
        }
    }

}
